package com.ai.zuochengyun.phase01.class07;

import com.ai.zuochengyun.phase01.class06.NodeHeap;

import java.util.*;

public class Code01_Dijkstra {

    public static void main(String[] args) {

    }

    public static Map<Node, Integer> dijkstra1(Node from) {
        Map<Node, Integer> distanceMap = new HashMap<>();
        distanceMap.put(from, 0);

        // 打过对号的点
        Set<Node> selectedNodes = new HashSet<>();
        Node minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
        while (minNode != null) {

            // 原始点到跳转点的最小距离
            int distance = distanceMap.get(minNode);
            for(Edge edge :minNode.edges) {
                Node toNode =  edge.to;

                if (!distanceMap.containsKey(toNode)) {
                    // 自己到自己的距离 加上 记下来要经过的边的权重
                    distanceMap.put(toNode, distance+edge.weight);
                } else {
                    // 当前边的权重和之前的值取较小的记录，作为下次比较的基准
                    distanceMap.put(toNode, Math.min(distanceMap.get(toNode), distance+edge.weight)) ;
                }
            }

            selectedNodes.add(minNode);
            minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
        }

        return distanceMap;
    }

    private static Node getMinDistanceAndUnselectedNode(Map<Node, Integer> distanceMap, Set<Node> selectedNodes) {
        Node minNode = null;
        // 默认无穷大
        int minDistance = Integer.MAX_VALUE;
        for(Map.Entry<Node, Integer> entry : distanceMap.entrySet()) {
            Node node = entry.getKey();
            int distance = entry.getValue();

            // 选择距离最小的节点
            if (!selectedNodes.contains(node) && distance < minDistance) {
                minNode = node;
                minDistance = distance;
            }
        }
        return minNode;
    }


    public static Map<Node, Integer> dijkstra2(Node head, int size) {
        NodeHeap nodeHeap = new NodeHeap(size);
        // 自己到自己的距离为0
        nodeHeap.addOrUpdateOrIgnore(head, 0);
        Map<Node, Integer> result = new HashMap<>();

        while (!nodeHeap.isEmpty()) {
            NodeRecord record = nodeHeap.pop();
            Node node = record.node;
            Integer distance = record.distance;
            for (Edge edge : node.edges) {
                nodeHeap.addOrUpdateOrIgnore(edge.to, distance +edge.weight);
            }
            result.put(node, distance);
        }
        return result;
    }
}
